package algorithm.middle;

import java.util.HashMap;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-02-27 21:43
 * @Description: 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aaabb", k = 3
 * 输出：3
 * 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestSubstring395 {

    //递归
    public int longestSubstring(String s, int k) {
        if(s.length() <k){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0;i<s.length();i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for (char key:map.keySet()){
            int res = 0;
            if (map.get(key)<k){
                //如果该字母小于k的个数，说明字串中不可能存在该字母，以该字母进行拆分进行递归
                for (String item:s.split(String.valueOf(key))){
                    res = Math.max(res,longestSubstring(item,k));
                }
                return res;
            }
        }
        return s.length();
    }

    /**
     * 递归最基本的是记住递归函数的含义（务必牢记函数定义）：本题的 longestSubstring(s, k) 函数表示的就是题意，即求一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 k。函数入参 s 是表示源字符串；k 是限制条件，即子字符串中每个字符最少出现的次数；函数返回结果是满足题意的最长子字符串长度。
     *
     * 递归的终止条件（能直接写出的最简单 case）：如果字符串 s 的长度少于 k，那么一定不存在满足题意的子字符串，返回 0；
     *
     * 调用递归（重点）：如果一个字符 ccc 在 s 中出现的次数少于 k 次，那么 s 中所有的包含 ccc 的子字符串都不能满足题意。所以，应该在 s 的所有不包含 ccc 的子字符串中继续寻找结果：把 s 按照 ccc 分割（分割后每个子串都不包含 ccc），得到很多子字符串 t；下一步要求 t 作为源字符串的时候，它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题(s → t)）。此时我们发现，恰好已经定义了函数 longestSubstring(s, k) 就是来解决这个问题的！所以直接把 longestSubstring(s, k) 函数拿来用，于是形成了递归。
     *
     * 未进入递归时的返回结果：如果 s 中的每个字符出现的次数都大于 k 次，那么 s 就是我们要求的字符串，直接返回该字符串的长度。
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/jie-ben-ti-bang-zhu-da-jia-li-jie-di-gui-obla/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
}
